package _06_动态规划;

import java.util.Arrays;

/**
 * https://leetcode-cn.com/problems/house-robber/
 *
 * @Author: haogege
 * @Date: 2021/9/11
 */
public class _198_打家劫舍 {

    public static void main(String[] args) {

        int[] ins = new int[]{1, 2, 3};
        _198_打家劫舍 v = new _198_打家劫舍();
        System.out.println(v.rob(ins));

    }

    public int rob(int[] nums) {
        if (nums.length == 1) return nums[0];
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < nums.length; i++) {
            dp[i] = Math.max(nums[i] + dp[i - 2], dp[i - 1]);
        }
        return dp[nums.length - 1];
    }

    // 变量优化
    public int rob4(int[] nums) {
        if (nums.length == 1) return nums[0];
        // 定义DP数组，为第i个之前房屋的最大偷窃价值
        // 初始化dp数组
        int prevAndPrev = nums[0];
        int prev = Math.max(nums[0], nums[1]);
        // 存在的情况，也就是偷与不偷的情况
        for (int i = 2; i < nums.length; i++) {
            int tmp = prev;
            prev = Math.max(prevAndPrev + nums[i], prev);
            prevAndPrev = tmp;
        }
        return prev;
    }

    // 滚动数组优化
    public int rob3(int[] nums) {
        if (nums.length == 1) return nums[0];

        // 定义DP数组，为第i个之前房屋的最大偷窃价值
        int[] dp = new int[2];
        // 初始化dp数组
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        // 存在的情况，也就是偷与不偷的情况
        for (int i = 2; i < nums.length; i++) {
            dp[i & 1] = Math.max(dp[i - 2 & 1] + nums[i], dp[i - 1 & 1]);
        }
        return dp[nums.length - 1 & 1];
    }

    // 本题是偷与不偷的问题
    public int rob2(int[] nums) {
        if (nums.length == 1) return nums[0];

        // 定义DP数组，为第i个之前房屋的最大偷窃价值
        int[] dp = new int[nums.length];
        // 初始化dp数组
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        // 存在的情况，也就是偷与不偷的情况
        for (int i = 2; i < nums.length; i++) {
            dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        return dp[nums.length - 1];
    }

    // 此解法是，如果偷到了第N个房间的最大值，求出每个的最大值，即可得出解
    public int rob1(int[] nums) {
        if (nums.length == 1) return nums[0];

        // 定义DP数组，为第i个之前房屋的最大偷窃价值
        int[] dp = new int[nums.length];
        // 初始化dp数组
        dp[0] = nums[0];
        dp[1] = nums[1];
        int result = Math.max(dp[0], dp[1]);
        for (int i = 2; i < nums.length; i++) {
            int max = dp[i - 2];
            for (int j = i - 2; j >= 0; j--) {
                // 寻找前n个的最大值
                max = Math.max(max, dp[j]);
            }
            dp[i] = max + nums[i];
            result = Math.max(result, dp[i]);
        }
        return result;
    }

}
